\begin{abstract}
We study the fundamental problem of information spreading (also known
as gossip) in dynamic networks.  In gossip, or more generally,
$k$-gossip, there are $k$ pieces of information (or tokens) that are
initially present in some nodes and the problem is to disseminate the
$k$ tokens to all nodes.  The goal is to accomplish the task in as few
rounds of distributed computation as possible.  The problem is
especially challenging in dynamic networks where the network topology
can change from round to round and can be controlled by an on-line
adversary.

The focus of this paper is on the power of token-forwarding
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  We first consider a worst-case
adversarial model first studied by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic} in which the communication links for
each round are chosen by an adversary, and nodes do not know who their
neighbors for the current round are before they broadcast their
messages. \junk{The model allows the study of the fundamental
  computation power of dynamic networks.}Our main result is an
$\Omega(nk/\log n)$ lower bound on the number of rounds needed for any
deterministic token-forwarding algorithm to solve $k$-gossip.  This
resolves an open problem raised in~\cite{kuhn+lo:dynamic}, improving
their lower bound of $\Omega(n \log k)$, and matching their upper
bound of $O(nk)$ to within a logarithmic factor.  Our lower bound also
extends to randomized algorithms against an adversary that knows in
each round the outcomes of the random coin tosses in that round.  Our
result shows that one cannot obtain significantly efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{kuhn+lo:dynamic}.  We next show that
token-forwarding algorithms can achieve subquadratic time in the
offline version of the problem, where the adversary has to commit all
the topology changes in advance at the beginning of the
computation. We present two polynomial-time offline token-forwarding
algorithms to solve $k$-gossip: (1) an $O(\min\{nk, n\sqrt{k \log
  n}\})$ round algorithm, and (2) an $(O(n^\eps), \log n)$ bicriteria
approximation algorithm, for any $\eps > 0$, which means that if $L$
is the number of rounds needed by an optimal algorithm, then our
approximation algorithm will complete in $O(n^\eps L)$ rounds and the
number of tokens transmitted on any edge is $O(\log n)$ in each
round. Our results are a step towards understanding the power and
limitation of token-forwarding algorithms in dynamic networks.
\end{abstract}
